#include "grafo.h"
#include "lista.h"



Grafo::Grafo()
{
    _cant_nodos = 0;
}

Grafo::Grafo(const int n, istream &is)
{
    cargar(n, is);
}

Grafo::~Grafo()
{
}

void Grafo::cargar(const int n, istream &is)
{

    lista_nodos.clear();
    grados.clear();
    _cant_nodos = n;

	for (int i = 0; i < n; i++) {
		int grado, pos;
		is >> grado;
		grados.push_back(grado);
		vector<int> ady_grado;
		for (int j = 0; j < grado; j++) {
			is >> pos;
			ady_grado.push_back(pos);
		}
		lista_nodos.push_back(ady_grado);
	}
}


ostream& operator<<(ostream& os, const Grafo& g) {

	cout << "Nodos: " << g.cant_nodos() << endl;
	for(int i = 0; i < g.cant_nodos(); i++){
					cout << "nodo " << i << " : " << "grado "<<g.grado(i) << ", ";
					for(int j = 0; j < g.grado(i); j++){
								cout << g.nodo_adyacente(i,j) << " ";
					}
					cout << endl;
	}
	return os;
}


vector<int> Grafo::lexBFS(){

	vector<int> res;
	ListaRefinada lex(_cant_nodos);
	/////
/*	cout << _cant_nodos << endl;
	lex.display();
	cout<<endl;*/
	/////
	//empiezo apuntando a la particion unica
	Double_linked< ListaRefinada::Particion >::Node* partptr = lex.lr.tail;

	int pivot = 0;
	vector<int> ady_pivot;
	//Double_linked< ListaRefinada::Particion >::Node* partptrAux = NULL;
	//ListaRefinada::Particion* pptr=NULL;
	Double_linked<int>::Node* idptr;
	Double_linked< ListaRefinada::Particion>::Node* npptr;

    //voy a tener que hacer cantnodos-1 iteraciones
	for(int i = 0; i < _cant_nodos - 1; i++){

		//apunto al vertice mas a la derecha de la particion
		pivot = ((partptr->data).vertices.tail)->data;
		//cout << "pivot: " << pivot << endl;
        res.push_back(pivot);




		idptr = lex.infoVertices[pivot].miNodo;
		ady_pivot = adyacencias(pivot);


		//separo al pivot en una particion unitaria, si es que no esta en una

            if(!((partptr->data).vertices.unitaria())){

                        //saco el nodo que voy a mover
                            (partptr->data).vertices.erase(idptr);

                        //creo la nueva particion

                           // pptr = new ListaRefinada::Particion();
                            npptr = new Double_linked<ListaRefinada::Particion>::Node(ListaRefinada::Particion(),NULL,NULL);
                            (npptr->data).vertices.pegarAtras(idptr);

                            //actualizo la info de particion del vertice
                            lex.infoVertices[pivot].miParticion = npptr;


                        // coloco la nueva a la derecha de la vieja

                         lex.lr.pegarADerechaDe(partptr,npptr);


                        //caso de borrado de particion vacia
                            if((partptr->data).vertices.empty()){
                                lex.lr.erase(partptr);
                                delete partptr;
                            }
            }


				//marco el pivot como visitado

				lex.infoVertices[pivot].visitado = true;

		//refino



		/*cout<<endl;
		lex.display();
		cout<<endl;*/


		lex.refinarDerecha(ady_pivot);

		/*cout<<endl;
        lex.display();
		cout<<endl;*/

		//ahora el pivot quedo aislado en una particion,
		//tomo el elemento mas a la derecha de la particion que la precede

		partptr = (lex.infoVertices[pivot].miParticion)->prev;

	}

	//agrego el ultimo vertice

	res.push_back(((((lex.lr.head)->data).vertices).head)->data);


	return res;

}

vector<int> Grafo::co_lexBFS(){

	vector<int> res;
	ListaRefinada lex(_cant_nodos);
	/////
/*	cout << _cant_nodos << endl;
	lex.display();
	cout<<endl;*/
	/////
	//empiezo apuntando a la particion unica
	Double_linked< ListaRefinada::Particion >::Node* partptr = lex.lr.tail;

	int pivot = 0;
	vector<int> ady_pivot;
	//Double_linked< ListaRefinada::Particion >::Node* partptrAux = NULL;
	//ListaRefinada::Particion* pptr=NULL;
	Double_linked<int>::Node* idptr;
	Double_linked< ListaRefinada::Particion>::Node* npptr;

//voy a tener que hacer cantnodos-1 iteraciones
	for(int i = 0; i < _cant_nodos - 1; i++){

		//apunto al vertice mas a la derecha de la particion
		pivot = ((partptr->data).vertices.tail)->data;
		//cout << "pivot: " << pivot << endl;
        res.push_back(pivot);




		idptr = lex.infoVertices[pivot].miNodo;
		ady_pivot = adyacencias(pivot);


		//separo al pivot en una particion unitaria, si es que no esta en una

            if(!((partptr->data).vertices.unitaria())){

                        //saco el nodo que voy a mover
                            (partptr->data).vertices.erase(idptr);

                        //creo la nueva particion

                           // pptr = new ListaRefinada::Particion();
                            npptr = new Double_linked<ListaRefinada::Particion>::Node(ListaRefinada::Particion(),NULL,NULL);
                            (npptr->data).vertices.pegarAtras(idptr);

                            //actualizo la info de particion del vertice
                            lex.infoVertices[pivot].miParticion = npptr;


                        // coloco la nueva a la derecha de la vieja

                         lex.lr.pegarADerechaDe(partptr,npptr);


                        //caso de borrado de particion vacia
                            if((partptr->data).vertices.empty()){
                                lex.lr.erase(partptr);
                                delete partptr;
                            }
            }


				//marco el pivot como visitado

				lex.infoVertices[pivot].visitado = true;

		//refino



		/*cout<<endl;
		lex.display();
		cout<<endl;*/


		lex.refinarIzquierda(ady_pivot);

		/*cout<<endl;
        lex.display();
		cout<<endl;*/

		//ahora el pivot quedo aislado en una particion,
		//tomo el elemento mas a la derecha de la particion que la precede

		partptr = (lex.infoVertices[pivot].miParticion)->prev;

	}

	//agrego el ultimo vertice

	res.push_back(((((lex.lr.head)->data).vertices).head)->data);


	return res;

}

